package main.java.sort;

import java.util.ArrayList;
import java.util.Collections;

/**
 * @Author: 郑国荣
 * @Date: 2023-10-04-16:38
 * @Description:
 */

public class BucketSort {
    public static void bucketSort(int[] array) {
        if (array == null || array.length == 0) {
            return;
        }

        int maxVal = array[0];
        int minVal = array[0];

        // 找到数组中的最大值和最小值
        for (int num : array) {
            if (num > maxVal) {
                maxVal = num;
            }
            if (num < minVal) {
                minVal = num;
            }
        }

        int bucketCount = maxVal - minVal + 1;// 桶的数量，相比计数哦排序更少
        ArrayList<Integer>[] buckets = new ArrayList[bucketCount];

        // 初始化桶
        for (int i = 0; i < bucketCount; i++) {
            buckets[i] = new ArrayList<>();
        }

        // 将元素放入对应的桶中
        for (int num : array) {
            buckets[num - minVal].add(num);
        }

        // 对每个桶内的元素进行排序
        int currentIndex = 0;
        for (int i = 0; i < bucketCount; i++) {
            Collections.sort(buckets[i]);
            for (int num : buckets[i]) {
                array[currentIndex++] = num;
            }
        }
    }

    public static void main(String[] args) {
        int[] array = {4, 2, 2, 8, 3, 3, 1};

        System.out.println("原始数组：");
        for (int num : array) {
            System.out.print(num + " ");
        }

        bucketSort(array);

        System.out.println("\n排序后的数组：");
        for (int num : array) {
            System.out.print(num + " ");
        }
    }
}

